package interview.美团;

import java.util.Scanner;

public class 题目三 {

//    逃离黑洞
//    时间限制： 3000MS
//    内存限制： 589824KB
//    题目描述：
//    小团驾驶着宇宙飞船在一个可视为H×W的二维空间宇宙中行驶（H对应纵坐标，W对应横坐标）。忽然，整个空间出现了n个黑洞（黑洞可以视为一个圆）。为了不碰到任意一个黑洞从而逃离这个空间（与黑洞边界有所接触即算碰到），小团要从(0,0)出发，抵达(H,W)从而穿越虫洞进行逃逸。小团有超能力，能够修改每个黑洞的半径，但是只能修改半径为非负整数，且修改后的半径越小，对他的身体负荷也就越大。小团想知道能够使他逃离的最大的黑洞半径可以是多少。黑洞保证不会出现在(0,0)与(H,W)。小团行驶过程中不能离开这个二维空间（不可以在空间边界）。
//
//
//
//    输入描述
//    第一行三个正整数n,H,W；
//
//    第二行输入n个整数xi，表示第i个黑洞中心（球心）的x轴坐标；
//
//    第三行输入n个整数yi，表示第i个黑洞中心的y轴坐标；
//
//    数字间两两空格隔开
//
//    对于100%的数据，1≤n≤1000，0≤xi,yi≤105，1≤H,W≤105，xi≤W,yi≤H
//
//            输出描述
//    输出一个非负整数r，表示能够使小团逃离的可修改的最大黑洞半径。
    // 9
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n,H,W;
        n = scanner.nextInt();
        H = scanner.nextInt();
        W = scanner.nextInt();
        int[][] group = new int[n][2];
        int[][] nums = new int[H + 1][W + 1];
        for (int i = 0; i < n; i++) {
            group[i][1] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            group[i][0] = scanner.nextInt();
        }
        int r = 0;
        do {
            markNums(nums, group, r, n);
            r++;
        } while (hasPath(nums));
        System.out.println(r - 1);
    }

    // 标记数组中不可达的点
    public static void markNums(int[][] nums, int[][] group, int r, int n) {
        int row = nums.length;
        int col = nums[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                for (int k = 0; k < n; k++) {
                    if (isInBorder(group[k][0], group[k][1], i, j, r)) {
                        nums[i][j] = -1;
                    }
                }
            }
        }
    }

    // 判断是否在黑洞内
    public static boolean isInBorder(int x, int y, int x1, int y1, int r){
        return (double)(x1 - x) * (x1 - x) + (double) (y1 - y) * (y1 - y) <= (double) r * r;
    }

    // 动规求能否到达终点
    public static boolean hasPath(int[][] nums) {
        int row = nums.length;
        int col = nums[0].length;
        boolean[][] visited = new boolean[row][col];
        boolean block = false;
        for (int i = 0; i < col; i++) {
            if (nums[0][i] != -1 && !block) {
                visited[0][i] = true;
            } else {
                block = true;
                visited[0][i] = false;
            }
        }
        block = false;
        for (int i = 0; i < row; i++) {
            if (nums[i][0] != -1 && !block) {
                visited[i][0] = true;
            } else {
                block = true;
                visited[i][0] = false;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (nums[i][j] == -1) {
                    visited[i][j] = false;
                } else {
                    visited[i][j] = visited[i -1][j] || visited[i][j - 1];
                }
            }
        }
        return visited[row - 1][col - 1];
    }
}
